package com.treeroot.queue;

/**
 * 循环数组队列
 * (rear + 1) % maxSize == front 是队列满的判定条件。
 * 下一个可添加元素的位置（rear + 1）
 * 要确定取模操作的除数，需要考虑的是队列的容量大小。
 * 由于循环队列中的存储空间是一个环形结构，所以我们可以认为队列的最大容量就是存储空间的长度，也就是 maxSize。
 * 因此，在计算下一个可添加元素的索引位置时，使用 (rear + 1) % maxSize 可以确保计算得到的索引值始终处于合法的范围内，避免了数组越界的情况发生
 * 在循环数组队列中，为了区分队列为空和队列为满两种情况，
 * 队列中不能填满所有元素，需要留一个空位。因此，队列中最多只能存放 maxSize - 1 个元素，
 * 当队列中元素个数达到 maxSize - 1 时，队列即为满。
 * 那么 (rear + 1) % maxSize 就是队列中下一个可添加元素的位置，
 * 如果它等于 front，则说明队列已经满了，因为队列头部指针 front 没有移动，队列尾部指针 rear 也无法再向前移动。
 * <>p</>
 * (front + 1) % maxSize 表示在循环数组队列中，下一个可出队元素的位置。
 * 当队列不为空时，通过 (front + 1) % maxSize 可以获取到队列头部元素的后面一个元素的位置，也就是下一个可出队元素的位置。
 * 因为队列头部指针 front 指向队列的第一个元素，所以应该选择 (front + 1) % maxSize 来获得下一个可出队元素的位置。
 * <>p</>
 * (rear + maxSize - front) % maxSize 表示在循环数组队列中，队列中有效数据的个数。
 * 在队列中，尽管元素并不是连续存储的，但是我们仍然可以通过计算获得队列中的有效数据个数。
 * 假设队列中有 maxSize 个元素，front 指向队列的第一个元素，rear 指向队列最后一个元素的下一个位置，
 * 那么像 (rear + maxSize - front) % maxSize 这样的计算方式可以保证计算出的是队列中有效数据的个数，
 * 即该计算式计算的结果等于 rear - front（当 rear >= front 时）或 rear - front + maxSize（当 rear < front 时）
 * -----------------------------------------------------------------------------------------------------
 * (rear + maxSize - front) % maxSize 是一种简便的方式来计算循环队列中的元素个数。
 * 具体来说，它的意义是：通过将队列的尾部指针 rear 与队列的头部指针 front 的差值加上队列的长度 maxSize，然后再对结果进行取模运算，可以得到当前队列中存储的元素个数。
 * 以下是具体的解释：
 * 假设当前循环队列的容量为 maxSize，队列的头结点是 front，尾结点是 rear，且头结点和尾结点之间间隔了 n 个有效元素。
 * 根据循环队列的定义，我们知道当头结点和尾结点相同时，队列为空，因此队列中的有效元素个数为 0；
 * 当 (rear + 1) % maxSize == front 时，队列已满，因此队列中的有效元素个数为 maxSize。
 * 而在其他情况下，队列中的有效元素个数就是尾结点与头结点之间间隔的元素个数，即 n。
 * 那么如何用 (rear + maxSize - front) % maxSize 来得出队列中的有效元素个数呢？
 * 我们将 (rear + maxSize - front) 理解成两部分：(rear - front) 和 maxSize。
 * 其中，(rear - front) 表示当前队列中元素间隔的距离，即有效元素的个数 n。
 * 当 (rear - front) < 0 时，表示尾结点在头结点之前，即队列元素发生了环绕，我们需要将 maxSize 加上差值 (rear - front)，以保证计算得到的结果是正数。
 * 最后，我们将计算出来的和对队列长度 maxSize 取模，就可以得到当前队列中存储的元素个数。
 * 举个例子，假设一个循环队列的容量为 10，头部指针为 5，尾部指针为 3，
 * 那么根据 (rear + maxSize - front) % maxSize 的计算公式，
 * 队列中的有效元素个数应该是 (3 + 10 - 5) % 10 = 8。这是因为队列中头部指针与尾部指针之间间隔了 8 个元素，即 8 个有效元素。
 */
public class CircleArrayByGPT {
    /**
     * 队列最大容量
     */
    private int maxSize;
    /**
     * 队列头部指针，指向队列的第一个元素
     */
    private int front;
    /**
     * 队列尾部指针，指向队列最后一个元素的下一个位置
     * 注意：为了区分队列为空和队列为满两种情况，队列中不能填满所有元素
     */
    private int rear;
    /**
     * 存储队列数据的数组
     */
    private int[] arr;

    public CircleArrayByGPT(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];
        front = 0;
        rear = 0;
    }

    /**
     * 判断队列是否已满
     *
     * @return 如果队列已满则返回true，否则返回false
     */
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    /**
     * 判断队列是否为空
     *
     * @return 如果队列为空则返回true，否则返回false
     */
    public boolean isEmpty() {
        return rear == front;
    }

    /**
     * 添加元素到队列尾部
     * (rear + 1) % maxSize 就是队列中下一个可添加元素的位置
     * 假如当前头指针1 最大容量4（只能放三个）===>  (1+1)%4 ==2 下一个位置就是2
     *
     * @param data 待添加的元素
     * @throws RuntimeException 如果队列已满则添加失败
     */
    public void add(int data) {
        if (isFull()) {
            System.out.println("队列已满，无法添加数据");
            throw new RuntimeException("队列已满，无法添加数据");
        } else {
            arr[rear] = data;
            rear = (rear + 1) % maxSize;
        }
    }

    /**
     * 获取队列头部元素,并删除
     * (front + 1) % maxSize 就是队列中下一个元素的出去的位置
     * 假如当前尾指针1 最大容量4（只能放三个）===>  (1+1)%4 ==2 下一个位置就是2
     *
     * @return 队列头部元素
     * @throws RuntimeException 如果队列为空则获取失败
     */
    public int getQueueData() {
        if (isEmpty()) {
            System.out.println("队列空异常");
            throw new RuntimeException("队列为空，无法取出数据");
        } else {
            int value = arr[front];
            front = (front + 1) % maxSize;
            return value;
        }
    }

    /**
     * 显示队列中的所有元素
     */
    public void showQueueData() {
        if (isEmpty()) {
            System.out.println("队列空~没有数据");
        } else {
            // 遍历队列从front到front+size之间的元素，其中size为队列中的有效数据个数
            for (int i = front; i < front + size(); i++) {
                System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i]);
            }
        }
    }

    /**
     * 获取队列中有效数据的个数
     *
     * @return 队列中有效数据的个数
     */
    public int size() {
        return (rear + maxSize - front) % maxSize;
    }

    /**
     * 显示队列头部元素
     *
     * @throws RuntimeException 如果队列为空则获取失败
     */
    public void showHeadData() {
        if (isEmpty()) {
            System.out.println("队列空异常");
            throw new RuntimeException("队列为空，无法取出数据");
        }
        System.out.printf("%d\n", arr[front]);
    }
}
